package com.dhj.top100;

import java.util.*;

public class ThreeSum {

    public static void main(String[] args) {
        System.out.println(threeSum3(new int[]{-1, 0, 1, 2, -1, -4}));
    }


    public static List<List<Integer>> threeSum3(int[] nums) {
        Arrays.sort(nums);
        int flipIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                flipIndex = i;
                break;
            }
        }
        String partition = "-";

        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= flipIndex; i++) {
            for (int j = flipIndex + 1; j < nums.length; j++) {
                int target = -(nums[i] + nums[j]);
                if (target >= 0) {
                    int k = j + 1;
                    while (k < nums.length && nums[k] < target) {
                        k++;
                    }
                    if (nums.length == k) {
                        continue;
                    }
                    String key = nums[i] + partition + nums[j] + partition + nums[k];
                    if (nums[k] + nums[i] + nums[j] == 0 && !map.containsKey(key)) {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        result.add(list);
                        map.put(key, 1);
                    }
                } else {
                    int k = 0;
                    while (k < i && nums[k] < target) {
                        k++;
                    }
                    if (i == k) {
                        continue;
                    }
                    String key = nums[k] + partition + nums[i] + partition + nums[j];
                    if (nums[k] + nums[i] + nums[j] == 0 && !map.containsKey(key)) {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        result.add(list);
                        map.put(key, 1);
                    }
                }
            }
        }

        return result;
    }

    public static List<List<Integer>> threeSum2(int[] nums) {
        // 如果全部元素都是0，则直接返回
        if (nums.length == 3 && (nums[0] + nums[1] + nums[2] == 0)) {
            return Collections.singletonList(Arrays.asList(nums[0], nums[1], nums[2]));
        }
        if (nums.length == 4 && (nums[0] + nums[1] + nums[2] == 0)) {
            return Collections.singletonList(Arrays.asList(nums[0], nums[1], nums[2]));
        }

        Arrays.sort(nums);
        int targetIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                targetIndex = i;
                break;
            }
        }
        String tag = "-";

        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= targetIndex; i++) {
            for (int j = targetIndex + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] >= 0) {
                    for (int k = i + 1; k <= targetIndex; k++) {
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                            String key = nums[i] + tag + nums[k] + tag + nums[j];
                            if (!map.containsKey(key)) {
                                result.add(list);
                                map.put(key, 1);
                            }
                        }
                    }
                } else {
                    for (int k = j + 1; k < nums.length; k++) {
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                            String key = nums[i] + tag + nums[j] + tag + nums[k];
                            if (!map.containsKey(key)) {
                                result.add(list);
                                map.put(key, 1);
                            }
                        }
                    }
                }

            }
        }

        return result;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                        list.sort(Comparator.naturalOrder());
                        if (!map.containsKey(String.valueOf(list))) {
                            result.add(list);
                            map.put(String.valueOf(list), 1);
                        }
                    }
                }
            }
        }

        return result;
    }

}
